// Copyright 2011 Jefferson Willian
// willmont7@gmail.com

#include <stdio.h>
#include <string.h>

#define MAX 201

int min(int a, int b, int c, char *move) {
  *move = 'E';

  if (b < a) {
    *move = 'I';
    a = b;
  }

  if (c < a) {
    *move = 'T';
    a = c;
  }

  return a;
}

int main() {
  int n, m;
  int i, j;
  int matriz[MAX][MAX];
  char moves[MAX][MAX];
  char dna[2][MAX];
  unsigned char buffer[MAX+1];
  char move;
  int games = 1;

  while (scanf("%s", dna[0]) && dna[0][0] != '#') {
    scanf("%s", dna[1]);

    n = strlen(dna[0]);
    m = strlen(dna[1]);

    for (int i = 1;i < n+1;i++) {
      matriz[i][0] = i;
      moves[i][0] = 'E';
    }

    for (int i = 1;i < m+1;i++) {
      matriz[0][i] = i;
      moves[0][i] = 'I';
    }

    /* Calcula o menor numero de operacoes sobre os genes */
    /* e grava o tipo de operacao:                        */
    /* T -> troca                                         */
    /* I -> inserir                                       */
    /* E -> excluir                                       */
    for (int i = 1;i < n+1;i++)
      for (int j = 1;j < m+1;j++) {
        if (dna[0][i-1] == dna[1][j-1]) {
          matriz[i][j] = matriz[i-1][j-1]+1;
          moves[i][j] = 'T';
        } else {
          matriz[i][j] = min(matriz[i-1][j]+1, matriz[i][j-1]+1, 100000, &move);
          moves[i][j] = move;
        }
      }

    buffer[0] = 0;

    /* Percorre a matriz de movimentos para montar o novo gene */
    while (1) {
      if (moves[n][m] == 'E')
        buffer[++buffer[0]] = dna[0][--n];
      else if (moves[n][m] == 'I')
        buffer[++buffer[0]] = dna[1][--m];
      else if (moves[n][m] == 'T' && dna[0][n-1] == dna[1][m-1]) {
        buffer[++buffer[0]] = dna[0][n--] = dna[1][--m];
      } else {
        buffer[++buffer[0]] = dna[1][--m];
        buffer[++buffer[0]] = dna[0][--n];
      }
      if (n == 0 && m == 0)
        break;
    }

    printf("Teste %d\n", games++);

    for (int i = buffer[0];i > 0;i--)
      printf("%c", buffer[i]);
    printf("\n\n");
  }

  return 0;
}
